#!/usr/bin/env python
# -*- coding: utf-8 -*-
'''
autor: Jose Jasnau Caeiro e António Baião

data: 7 de maio de 2012
aletarado - 15 de junho de 2012

arvores de pesquisa binária
'''
from Stack import Stack
import math
import sys
from QuickSort import quicksort

'''
Classe No
Usada para criar os nós que estarão presentes na árvore
Para alem da normal estrutura do no
tem ainda a profundidade a que vai ficar e o index que ocupa na stack
'''
class No:
    def __init__(self):
        self.key = None
        self.index = None
        self.depth = None
        self.parent = None
        self.left = None
        self.right = None
        pass

    def __str__(self):
        s = str(self.index) + " - "
        
        s += str(self.depth) + " # "
        
        s += str(self.key)
        
        s += '('
        if self.parent == None:
            s += 'None' + ', ' 
        else:
            s += str(self.parent) + ', ' 

        if self.left == None:
            s += 'None' + ', ' 
        else:
            s += str(self.left) + ', ' 

        if self.right == None:
            s += 'None' + ')' 
        else:
            s += str(self.right) + ')' 
            
        return s

'''
Class responsavel pela  criação da arvore k-d
bem como todos as suas tarefas
'''
class k_d_tree:
    '''
    Contrutor incializa a stack
    Incializa as variaveis de contrlo como
    o contador de nos "nNo" usado no calculo da profundidade
    Inicaliza a lista que vai conter as chaves
    '''
    def __init__(self, N):
        self.apontadores_memoria = Stack(N)
        self.N = N
        for k in range(N):
            self.apontadores_memoria.push(k)
        self.nNo = None #Armazena o numero de nos de uma subarvore  
        self.maxNNo = None #Armazena o maior numero de nos precorrido  
        self.root = None
        self.count = None
        
        self.keys = [None for k in range(N)]
    '''
    Responsavel por realizar as alocações de memoria na stack sempre que
    se inser um novo nó
    '''
    def malloc(self, k):
        if self.apontadores_memoria.top != 0:
        
            x = self.apontadores_memoria.pop()
        
            self.keys[x] = k
            
            return x
            pass
        else:
            print "Pilha cheia"
            
            pass
    
    '''
    Liberta o espaço da stack ocupado pelo item que se pertende eliminar
    '''
    def free(self, x):
        self.apontadores_memoria.push(x)


    '''
    Método responsavel por contruir a K-d tree
    Recebe para isso uma lista de elementos 
    Ordena-os e divide os seus planos pela sua mediana
    construindo assim uma arvore totalmente balanceada
    '''
    def kdtree(self, point_list, depth=0, parent=None):
       
        if not point_list:
            return None
 
    # Select axis based on depth so that axis cycles through all valid values
        k = len(point_list[0]) # assumes all points have the same dimension
        
        axis = depth % k
        
    # Sort point list and choose median as pivot element
        quicksort(point_list, 0, len(point_list) - 1, axis)
        #point_list.sort(key=lambda point: point[axis])
        median = len(point_list) // 2 # choose median
 
    # Create node and construct subtrees
        
        node = No()
        x = self.malloc(node)
        self.keys[x].depth = axis
        self.keys[x].index = x
        self.keys[x].parent = parent
        self.keys[x].key = point_list[median]
        self.keys[x].left = self.kdtree(point_list[:median], depth + 1, x)
        self.keys[x].right = self.kdtree(point_list[median + 1:], depth + 1, x)
      
        
        
        
        if self.count == 1:
            self.root = x
            #print self.root
            
            #print "entei aqui uma vez"
        else:
            self.count -= 1
            
            pass
        
      
            
        return x

    def print_list(self):
        
       
        for x in range(len(self.keys)):
            print str(x) + " - " + str(self.keys[x])
        pass
    '''
    Insere os nós na árvore
    Este metodo é antecedido do metodo malloc que primeiramente vai alocar memoria
    para a inserção
    de resto esta processa de forma semelhante que na árvore binária tendo apenas em atenção a dimensão da
    chave
    '''
    def insert(self, z):
        y = None
        x = self.root
        depth = 0
        usingKey = -1
        keyLen = len(self.keys[x].key)
        self.keys[z].index = z
        while x != None:
            y = x
            
            #print y
            
            if usingKey == keyLen - 1:
                usingKey = 0
                #print "entrei"
            else:
                usingKey += 1
                
           
            if self.keys[z].key[usingKey] < self.keys[x].key[usingKey]:
                x = self.keys[x].left
            else:
                x = self.keys[x].right
                
            depth += 1
            #################################################################
     
        self.keys[z].depth = usingKey
        self.keys[z].parent = y
        if y == None:
            self.root = z
        elif self.keys[z].key[usingKey] < self.keys[y].key[usingKey]:
            self.keys[y].left = z
        else:
            self.keys[y].right = z

    '''
    Método que procuara todos os nos folha de um lado da arvore para depois 
    calcular com auxilio de  outro metodo
    qual o mais profundo
    este método é usado para saber se a arvore esta ou não balanceada
    '''
    def serchForLeafNo(self, side):
        self.maxNNo = 0
        self.nNo = 1    
        parentTemp = None
        
        if self.keys[self.root].left == None and self.keys[self.root].left == None:
            return 1
        else:
            if side == 0:
                parentTemp = self.keys[self.root].left
            else:
                parentTemp = self.keys[self.root].right
             
        
        examineNos = []
        
        for x in self.keys:
            if x != None:
                
                if x.parent == parentTemp:
                    examineNos.append(x)
                    
        for a in examineNos:
            if(a.left != None):
                examineNos.append(self.keys[a.left])
            elif(a.right != None):
                examineNos.append(self.keys[a.right])
             
        
        leafNodes = []
        
        for noE in examineNos:
            if noE.left == None and noE.right == None:
                
                leafNodes.append(noE)
       
        
        for ln in leafNodes:
            
            self.howManyStepsToRoot(ln)    
                
        
        return self.maxNNo
                
    '''
    Conta quantos nos temos que precorrer desde o no folha ate a raiz
    este método é axuliar do anterior
    '''
    def howManyStepsToRoot(self, noLeaf):
        
        x = noLeaf.index
        while self.keys[x].parent != None:
            x = self.keys[x].parent
            self.nNo += 1
            
            
        if self.nNo > self.maxNNo:
            self.maxNNo = self.nNo
        
        self.nNo = 1

    '''
    Procura por um determinado nó
    Este metodo recebe um elemento no formato de chave dimensional
    ex:[3,4]
    '''            
    def search(self, x, k):
        if self.keys[x] == None or k == self.keys[x].key:
            return x
        if k[self.keys[x].depth] < self.keys[x].key[self.keys[x].depth]:
            return self.search(self.keys[x].left, k)
        else:
            return self.search(self.keys[x].right, k)

    '''
    este método vai ser responsavel por precorrer 
    a árvore e procurar com ajuda do metodo auxiliar 
    o vizinho mais procximo do nó
    que fica na posição dada
    '''
    def searchNearestNeighbour(self, x):
        bestDisntance = sys.maxint
        nearestNode = None
        tempList = []
        self.inorder_walk(self.root, tempList)
        for no in tempList:
            
            
                if no.key != self.keys[x].key:
                    distance = self.calculateDistance(self.keys[x], no)
               
                    if distance < bestDisntance:
                    
                        bestDisntance = distance
                    
                        nearestNode = no.index                
                        pass
                   
            
                    
        return nearestNode
            
                 
    '''
    Calcula a distancia euclidiana entre um nó e outro
    é usado como auxiliar do de cima
    '''
    def calculateDistance(self, oNo, nNo):
        keyDimension = len(oNo.key)
        
        distance = 0
        for x in range(keyDimension - 1):
            distance += math.pow((oNo.key[x] - nNo.key[x]), 2)
            
        distance = math.sqrt(distance)
        return distance
    
    '''
    Calcula o minimo da árvore
    '''     
    def minimum(self, x):
        self.nNo = 1
        while self.keys[x].left != None:
            x = self.keys[x].left
            self.nNo += 1
     
        return x
    '''
    Calcula o minimo da árvore
    ''' 
    def maximum(self, x):
        self.nNo = 1
        while self.keys[x].right != None:
            self.nNo += 1
            x = self.keys[x].right
            
            
       
        return x
    '''
    procura qual o successor de um dado nó
    este metodo recebe o indice do no a que se procurar o sucessor
    O sucessor é o nó com valor mais pequeno mas maior que o que se procura
    '''
    def sucessor(self, x):
        if self.keys[x].right != None:
            return self.minimum(self.keys[x].right)
        y = self.keys[x].parent
        while y != None and x == self.keys[y].right:
            x = y
            y = self.keys[y].parent
        return y
    '''
    usado para reorganizar uma parte da árvore sempre
    que é apagado um elemnto
    é auxliar do metodo em baixo
    '''
    def transplant(self, u, v):
        if self.keys[u].parent == None:
            self.root = v
        elif u == self.keys[self.keys[u].parent].left:
            self.keys[self.keys[u].parent].left = v
        else:
            self.keys[self.keys[u].parent].right = v
        if v != None:
            self.keys[v].parent = self.keys[u].parent
    '''
    é responsavel por apagar um elento dado
    o elemnto é dado sobe a forma do seu indice
    depois de eleminado é libertada a sua posição na memoria
    '''
    def delete(self, z):
        if self.keys[z].left == None:
            self.transplant(z, self.keys[z].right)
        elif self.keys[z].right == None:
            self.transplant(z, self.keys[z].left)
        else:
            y = self.minimum(self.keys[z].right)
            if self.keys[y].parent != z:
                self.transplant(y, self.keys[y].right)
                self.keys[y].right = self.keys[z].right
                self.keys[self.keys[y].right].parent = y
            self.transplant(z, y)
            self.keys[y].left = self.keys[z].left
            self.keys[self.keys[y].left].parent = y

    '''
    Fáz uma consulta ordenada á árvore
    '''
    def inorder_walk(self, x, lista):
        
        if x != None:
        
            if self.keys[x] != None:
                self.inorder_walk(self.keys[x].left, lista)
                lista.append(self.keys[x])
                self.inorder_walk(self.keys[x].right, lista)  
            
                
    pass
    '''
    Responsavel por rebalancear a arvore caso esta necessite
    é ajudado por metodo auxiliar
    se a airvore precisar de ser rebalanceada, controi um novo conjunto com os nos e é envia-os para se cirar novamente 
    a árvore
    '''
    def reBalanceTree(self):
        
        if(self.checkIsBalanced() == False):
            
            #Lista onde terão todos os nos
            list = []
        
            self.inorder_walk(self.root, list)
        
            #lista onde serão armazenadas todas a chaves
            listKeys = []
        
            #cria lista com todas as chaves
            for x in list:
                listKeys.append(x.key)
                self.free(x.index)
                self.keys = [None for k in range(self.N)]
        
            self.count = len(listKeys)
            self.kdtree(listKeys)
        else:
            
            print "Não é necessário por enquanto"
            
            pass
    '''
    Verifica se a arvore está balanciada.
    Segundo os critérios de balanceamento
    ambos os lados da arvore nao pode ter uma diferença de distancia máxima do nó
    raiz até ao nó mais profundo superior a 1. Caso for maior que 1 a arvore nao esta balanceada
    
    '''
    def checkIsBalanced(self):
        
        leftSide = self.serchForLeafNo(0)
        rightSide = self.serchForLeafNo(1)
        if(leftSide > rightSide):
            if (leftSide - rightSide) > 1:
                return False
            else:
                return True
        else:
            if (rightSide - leftSide) > 1:
                return False
            else:
                return True
        
        pass
